<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 6.0.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/wang-cheng/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/wang-cheng/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/wang-cheng/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/wang-cheng/images/logo.svg" color="#222">

<link rel="stylesheet" href="/wang-cheng/css/main.css">


<link rel="stylesheet" href="/wang-cheng/lib/font-awesome/css/all.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"cheng-wang123.gitee.io","root":"/wang-cheng/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}}};
  </script>

  <meta name="description" content="哈希函数与哈希表等哈希结构 无限个输入、有限个输出  例如：MD5加密算法就是采用哈希底层的算法实现， MD5的取值范围为0~2^64-1。所以可以输入任何的对象，但它只会给你返回给一个有限值   相同的输入，一定会有一个相同的输出。也就是说你输入相同的对象，输出的哈希值一定相同  不同的输入、可能会输出相同的值。因为哈希值是有限的，输入两个不同的对象也可能获得相同的值。这种情况被称为哈希碰撞(可">
<meta property="og:type" content="article">
<meta property="og:title" content="算法笔记(四)">
<meta property="og:url" content="https://cheng-wang123.gitee.io/wang-cheng/2022/04/02/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E5%9B%9B/index.html">
<meta property="og:site_name" content="诚の博客">
<meta property="og:description" content="哈希函数与哈希表等哈希结构 无限个输入、有限个输出  例如：MD5加密算法就是采用哈希底层的算法实现， MD5的取值范围为0~2^64-1。所以可以输入任何的对象，但它只会给你返回给一个有限值   相同的输入，一定会有一个相同的输出。也就是说你输入相同的对象，输出的哈希值一定相同  不同的输入、可能会输出相同的值。因为哈希值是有限的，输入两个不同的对象也可能获得相同的值。这种情况被称为哈希碰撞(可">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2022-04-02T11:26:21.000Z">
<meta property="article:modified_time" content="2022-04-26T08:04:15.768Z">
<meta property="article:author" content="王诚">
<meta property="article:tag" content="左神">
<meta name="twitter:card" content="summary">

<link rel="canonical" href="https://cheng-wang123.gitee.io/wang-cheng/2022/04/02/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E5%9B%9B/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>算法笔记(四) | 诚の博客</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

<link rel="alternate" href="/wang-cheng/atom.xml" title="诚の博客" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/wang-cheng/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">诚の博客</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">记录学习中的点点滴滴</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/wang-cheng/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/wang-cheng/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/wang-cheng/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/wang-cheng/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
  </ul>
</nav>




</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://cheng-wang123.gitee.io/wang-cheng/2022/04/02/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E5%9B%9B/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/wang-cheng/images/avatar.gif">
      <meta itemprop="name" content="王诚">
      <meta itemprop="description" content="命运对勇士低语，你无法抵御风暴；勇士低声回应，我就是风暴">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="诚の博客">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          算法笔记(四)
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2022-04-02 19:26:21" itemprop="dateCreated datePublished" datetime="2022-04-02T19:26:21+08:00">2022-04-02</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2022-04-26 16:04:15" itemprop="dateModified" datetime="2022-04-26T16:04:15+08:00">2022-04-26</time>
              </span>

          
            <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv" style="display: none;">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span id="busuanzi_value_page_pv"></span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="哈希函数与哈希表等"><a href="#哈希函数与哈希表等" class="headerlink" title="哈希函数与哈希表等"></a><strong>哈希函数与哈希表等</strong></h1><h2 id="哈希结构"><a href="#哈希结构" class="headerlink" title="哈希结构"></a><strong>哈希结构</strong></h2><ol>
<li><p>无限个输入、有限个输出</p>
<ul>
<li>例如：MD5加密算法就是采用哈希底层的算法实现， MD5的取值范围为0~2^64-1。所以可以输入任何的对象，但它只会给你返回给一个有限值</li>
</ul>
</li>
<li><p>相同的输入，一定会有一个相同的输出。也就是说你输入相同的对象，输出的哈希值一定相同</p>
</li>
<li><p>不同的输入、可能会输出相同的值。因为哈希值是有限的，输入两个不同的对象也可能获得相同的值。这种情况被称为哈希碰撞(可能性极低)</p>
</li>
<li><p>假设将哈希函数的输出范围看作一个域S。每输入一个值，都可以看作是在S上的一个点。</p>
<ul>
<li>哈希函数最重要的性质是：它可以将这些点均匀的分布在域S上，使得它的均匀性和离散型都能得到保证<ul>
<li>离散型:不同的输入，离散到S上的位置是没规律的。离散性越好，哈希函数越好。</li>
</ul>
</li>
</ul>
</li>
</ol>
<h2 id="哈希表的实现"><a href="#哈希表的实现" class="headerlink" title="哈希表的实现"></a><strong>哈希表的实现</strong></h2><h3 id="哈希表是如何将时间复杂度逼近为O-1-的"><a href="#哈希表是如何将时间复杂度逼近为O-1-的" class="headerlink" title="哈希表是如何将时间复杂度逼近为O(1)的"></a><strong>哈希表是如何将时间复杂度逼近为O(1)的</strong></h3><p>假设现在哈希表的长度为17</p>
<p>再假设现在向哈希表中放入一个对象，假设为’abc’，对应值为34。</p>
<ol>
<li><p>哈希表对’abc’调用一个哈希函数，得出一个值out1</p>
</li>
<li><p>out1%17，会得到一个具体的值，这个值在哈希表中具有具体的位置。假设为13。</p>
</li>
<li><p>找到哈希表中下标为13的位置，在这个位置串一张单链表，单链表节点为’abc’,伴随值为34.</p>
</li>
<li><p>假设又放入一个对象，调用完哈希函数，取完模之后的的值也是13，就在单链表的尾部再串一个节点</p>
</li>
</ol>
<p>问题:如果加入大量对象，那么哈希表中的链就会很长。怎么办呢？</p>
<p><strong>哈希表减小时间复杂度的第一个技术：利用哈希函数与链表相结合的方式达到目标</strong></p>
<p>在哈希表中，定义一个变量，统计每个数组中链表的长度，如果长度超过了6，就触发扩容逻辑(当哈希表的链表长度过长，增删改查的速度也会随之降低，一般哈希表增上改查的时间复杂度是小于O(logN))。因为哈希函数具有离散性和均匀性，所以其他链表的长度也接近于6了。</p>
<p>触发扩容机制后，会新建一张哈希表，如果之前哈希表的长度为17，新建的这张表的长度则为34。然后原先表中的元素会重新算一遍哈希值，然后放到新表中。</p>
<p>时间复杂度的分析：找一个在哈希表中的对象，只需要算它的哈希函数，所以时间复杂度是O(1)，但这个复杂度的常识很大，取模的时间复杂度也是O(1)。然后去数组中去找，如果我的链表的长度为k，那么我的时间复杂度就是O(K),如果保证这个链表的长度不会过长，那么它就可以看作是O(1)。但是链表过长的时候是会触发扩容的，扩容的代价怎么算？</p>
<p>扩容代价的计算：如果我向哈希表中加入了N个对象，则会触发logN次扩容(实际中远远小于logN,但也只是在常数级别小于logN)。每次扩容，都需要将原来哈希表中的N个对象重新计算哈希值重新存入新哈希表，所以它的时间复杂度为O(N)。则总的代价为O(N*logN)。而这是计算的一共扩容logN次的代价，所以每一次扩容的代价为O(logN)。</p>
<p>但是为什么说哈希表在使用的时候，时间复杂度一般为O(1)呢？因为哈希表可以将K定义得很长，也不会很大的影响我的时间复杂度O(K)，但是可以极大的减小我的扩容代价。所以这个O(logN)就成为了一个特别小的常数的一个数，则这个O(logN)就会慢慢逼近O(1)。</p>
<p><strong>哈希表减小时间复杂度的第二个技术:离线扩容</strong></p>
<p>JVM在使用哈希表的时候，在不影响原先表使用的情况下，可以新建一张哈希表，当原表存入对象过多，可以把引用对象切换到新表上。这样可以在不占用用户时间的情况下，实现扩容，再次将时间复杂度变得很低。</p>
<p><strong>所以，哈希表的增删改查虽然在理论上来说时间复杂度是O(logN)，但是在实际中是可以看作O(1)的</strong></p>
<p>哈希表在Java中还有所改进，将链表改为了二叉树</p>
<h2 id="详解布隆过滤器"><a href="#详解布隆过滤器" class="headerlink" title="详解布隆过滤器"></a><strong>详解布隆过滤器</strong></h2><h3 id="字节-Byte-与比特-bit-之间的关系"><a href="#字节-Byte-与比特-bit-之间的关系" class="headerlink" title="字节(Byte)与比特(bit)之间的关系"></a><strong>字节(Byte)与比特(bit)之间的关系</strong></h3><p>计算机存储单位一般用bit、B、KB、MB、GB、TB、PB、EB、ZB、YB、BB、NB、DB……来表示，它们之间的关系是</p>
<p>位 bit (比特)(Binary Digits)：存放一位二进制数，即 0 或 1，最小的存储单位</p>
<p>字节byte：8个二进制位为一个字节(B)，最常用的单位。</p>
<p>1 Byte（B） = 8 bit</p>
<p>1 Kilo Byte（KB） = 1024B</p>
<p>1 Mega Byte（MB） = 1024 KB</p>
<p>1 Giga Byte （GB）= 1024 MB</p>
<p>1 Tera Byte（TB）= 1024 GB</p>
<p>1 Peta Byte（PB） = 1024 TB</p>
<h3 id="布隆过滤器的原理"><a href="#布隆过滤器的原理" class="headerlink" title="布隆过滤器的原理"></a><strong>布隆过滤器的原理</strong></h3><p>0~m-1，长度为m的bit类型的结构，实际占用空间为m/8个字节(电脑统计空间都用字节)的内存。</p>
<p>每个url，调用哈希函数，算出k个哈希值，模上一个数m，得到k个位置。将这k个位置标记下来。</p>
<p>当去查询这个黑名单，通过url算出哈希值，模上m，得到k位置，查看这k个位置有没有被标记，如果这个url是黑名单里的数，那么这个url一定被标记过</p>
<p>失误率是由m和k决定的。如果m过小，数据量过大，经过上面的操作后，整个结构可能都变成被标记的，那么无论查哪个url都是黑名单里的url。</p>
<p>k可以形象的看作是采集指纹，k越大，得到的位置越多，url越精确，不同的url算出在同一个位置的概率较小，也可以降低失误率。</p>
<p>可以先确定m需要定多大，然后根据已经确定的参数计算出有多少个哈希函数是合适的。</p>
<h3 id="面试中聊到布隆过滤器"><a href="#面试中聊到布隆过滤器" class="headerlink" title="面试中聊到布隆过滤器"></a><strong>面试中聊到布隆过滤器</strong></h3><p>设计过滤器，只需要确定是不是这个模型(集合结构，没有删除行为，类似黑名单查询的)、有没有失误率</p>
<ol>
<li><p>在跟面试官聊的时候，要回答什么时候可以用过滤器—&gt;类似于黑名单，而且没有删除行为的</p>
</li>
<li><p>问面试官：这个系统允不允许有失误率  如果面试官说允许，那么他考你的就是过滤器。</p>
</li>
<li><p>既然允许，那么就需要问他，他的失误率预期是多少</p>
</li>
</ol>
<p>注意:布隆过滤器只和样本量、失误率两个参数有关。与单一样本的大小没有关系。</p>
<script type="math/tex; mode=display">公式: m = -\frac{n*lnp}{(ln2)^2} \quad</script><p>n = 100亿、p = 0.0001带进去，算出m的值，算出来的数除以8才是实际占用的内存</p>
<p>这个结果大约26G</p>
<script type="math/tex; mode=display">公式: k = 0.7* \frac{m}{n} \quad</script><p>k的值可能是小数，向上取整(取整后为k(真))。k为需要的哈希函数个数。</p>
<p>这里需要注意:上面算出来的内存为26G，这个内存是达到这个失误率的最小内存了，如果我的内存可以更大一些m(真)，那么我的失误率将会再次降低，而要求这个失误率为多少，也会公式：</p>
<script type="math/tex; mode=display">p(真)=(1-{\rm e}^x)^{k(真)}</script><script type="math/tex; mode=display">x = -\frac{n*k(真)}{m(真)} \quad</script><p>布隆过滤器优缺点</p>
<p>优点：</p>
<ul>
<li>节省空间：不需要存储数据本身，只需要存储数据对应hash比特位</li>
<li>时间复杂度低：插入和查找的时间复杂度都为O(k)，k为哈希函数的个数</li>
</ul>
<p>缺点：</p>
<ul>
<li>存在假阳性：布隆过滤器判断存在，可能出现元素不在集合中；判断准确率取决于哈希函数的个数</li>
<li>不能删除元素：如果一个元素被删除，但是却不能从布隆过滤器中删除，这也是造成假阳性的原因了</li>
</ul>
<p>布隆过滤器适用场景</p>
<ul>
<li>爬虫系统url去重</li>
<li>垃圾邮件过滤</li>
<li>黑名单</li>
</ul>
<hr>
<h2 id="一致性哈希原理"><a href="#一致性哈希原理" class="headerlink" title="一致性哈希原理"></a><strong>一致性哈希原理</strong></h2><p>后端程序员基本必考</p>
<p>一种特殊的哈希算法，目的是解决分布式缓存的问题</p>
<p>在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。一致性哈希解决了简单哈希算法在分布式哈希表中存在的动态伸缩等问题</p>
<p>在分布式问题当中，数据服务器可能需要存大量数据，一台服务器可能承担不下来，所以需要多台服务器来完成数据的存储，这个时候就存在了一个问题：数据到底存到哪台服务器上。</p>
<p>经典分布式数据库的设计:</p>
<p>当逻辑端需要存数据时，将这个数据调用一个哈希函数，算出来一个值，再模上你服务器的数量</p>
<p>但这种设计方式存在一个问题，如果我需要删除或添加一台服务器，那么之前我用模服务器数量的方式就不能用了，那么这些服务器上的数据都需要重新算一遍哈希值然后模一下服务器的数量。增加机器和删除机器，数据迁移是全量的。</p>
<p>解决这个问题，就是想办法怎样不用模的方式来分配数据，让迁移量不会达到全量。</p>
<h3 id="一致性哈希解决"><a href="#一致性哈希解决" class="headerlink" title="一致性哈希解决"></a><strong>一致性哈希解决</strong></h3><p>这里用MD5算法来举例，MD5的范围是0~2^64-1</p>
<ul>
<li><p>将这个范围想象成一个环。对服务器通过哈希函数，算出一个哈希值。</p>
</li>
<li><p>多个服务器可以算出多个哈希值，哈希值对应环中的某个点，就可以想象成将这些服务器插入到了环中</p>
</li>
<li><p>当逻辑服务器需要存储数据到数据服务器时，将数据通过哈希函数算出一个哈希值，这个哈希值一定会在环上的某个位置。</p>
</li>
<li><p>直到这个位置之后，按照位置将数据放到顺时针离我最近的那台机器上。</p>
</li>
</ul>
<p>通过一个request确定存到哪台服务器的实现机制是什么？</p>
<p>机制实现:在逻辑端，将数据端服务器的哈希值进行一个排序，存入到逻辑端服务器中的数组中。</p>
<p>当我要存一个数据，通过哈希函数算出来一个哈希值。然后在逻辑服务器里面的存服务器哈希值的数组中做二分查找，就可以找到大于等于这个哈希值最左边的那个数。就可以知道这个数据要存入哪个数据服务器了。如果找不到大于等于这个哈希值的数，那么就将这个数存入到哈希值最小的那台服务器上(因为是环状)</p>
<p><strong>与经典分布式数据库相比的好处:</strong></p>
<p>数据服务器的增加、删除时，数据迁移量很低，因为每个服务器都在环上，当添加一台服务器或者删除一台服务器时，并不需要取模(避免了全量迁移),而是只需要迁移一部分。</p>
<p><strong>存在的问题</strong></p>
<ol>
<li><p>数据服务器数量很少的时候，可能一上来不一定做到环的均分(因为要考虑负载均衡)。</p>
</li>
<li><p>即便我服务器数量很少，一上来就能对环做到均分，但是当我增加或减少一台服务器时，就不能对环做到均分了。</p>
</li>
</ol>
<h3 id="解决一致性哈希存在的两个问题"><a href="#解决一致性哈希存在的两个问题" class="headerlink" title="解决一致性哈希存在的两个问题"></a><strong>解决一致性哈希存在的两个问题</strong></h3><p><strong>虚拟节点技术</strong></p>
<p>对每台数据服务器，都给他分配1000字符串(不一定是1000，举例)。可以看作每一台服务器都有1000个虚拟点，都是1000个代表字符串。</p>
<p>对每一个字符串都算出一个哈希值，当作环中的一个点。</p>
<p>这个技术很好的解决了服务器数量少和增删服务器时对环做不到均分的问题了。</p>
<p>虚拟节点之间数据的迁移也是很好实现的。因为每个服务器都有实际的路由表，查找到需要迁移数据的虚拟节点和接收数据迁移的虚拟节点，然后将数据传递过去就可以了。</p>
<p><strong>一致性哈希还可以管理负载</strong></p>
<p>如果一台服务器的性能很强，那么在分配字符串时可以多给它分配一些字符串，如果一台服务器的性能很弱，那么在分配字符串时就可以少给他分配一些字符串。</p>
<p>这样就可以通过这种方式实现负载的管理。</p>
<p><strong>现在各大公司底层分布式数据库都用到了这个原理</strong>，这篇论文被誉为谷歌改变世界三驾马车之一。</p>
<p><strong>一致性哈希算法的简单概述</strong></p>
<p>一致性哈希算法将整个哈希值空间映射成一个虚拟的圆环，整个哈希空间的取值范围为0~232-1。</p>
<p>整个空间按顺时针方向组织。0~232-1在零点中方向重合。接下来使用如下算法对服务请求进行映射，将服务请求使用哈希算法算出对应的hash值，然后根据hash值的位置沿圆环顺时针查找，第一台遇到的服务器就是所对应的处理请求服务器。当增加一台新的服务器，受影响的数据仅仅是新添加的服务器到其环空间中前一台的服务器（也就是顺着逆时针方向遇到的第一台服务器）之间的数据，其他都不会受到影响。综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。</p>
<hr>
<h2 id="并查集"><a href="#并查集" class="headerlink" title="并查集"></a><strong>并查集</strong></h2><p>题目：一个矩阵只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛</p>
<hr>
<p>并查集结构:</p>
<p>{a},{b},{c},{d},{e}</p>
<p>提供两个操作，查询两个样本是否属于一个集合、合并两个集合</p>
<p>经典结构都不太合适，所以提供了一个并查集结构。</p>
<p>把每一个样本当作一个图，上述集合中因为都是一个样本是一个集合，所以将一个样本看作一个单独的图，图的节点指向自己。</p>
<p><strong>查询两个样本是否属于一个集合</strong></p>
<p>{a},{b}</p>
<p>通过找两个集合中往上指的指针，找到最后一个元素(代表元素)，看两个集合的代表元素是否相同，相同则是同一个集合，不相同则不是同一个集合。</p>
<p><strong>优化查询</strong></p>
<p>在合并集合的过程中，可能往上指的链存在过长的情况，使得查询速度降低。这时候可以在查询两个样本是否属于一个集合的过程后，将这条路径上的所有节点都指向顶部元素，这样下次再查找的时候就能一步到位。</p>
<p><strong>合并两个集合成为一个集合</strong><br>通过找两个集合中往上指的指针，看最顶节点哪个被指向的多，数量较少的集合的顶端，要挂在数量较多的顶端的底下。</p>
<figure class="highlight reasonml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br></pre></td><td class="code"><pre><span class="line">public static <span class="keyword">class</span> Element&lt;V&gt;&#123;</span><br><span class="line">    public V value;</span><br><span class="line">    public <span class="constructor">Element(V <span class="params">value</span>)</span>&#123;</span><br><span class="line">        this.value = value;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">public static <span class="keyword">class</span> UnionFindSet&lt;V&gt;&#123;</span><br><span class="line">    public HashMap&lt;V,Element&lt;V&gt;&gt; elementMap;</span><br><span class="line">    <span class="comment">// key 某个元素，value 该元素的父</span></span><br><span class="line">    public HashMap&lt;Element&lt;V&gt;,Element&lt;V&gt;&gt; fatherMap;</span><br><span class="line">    <span class="comment">//key 表示代表节点,value表示代表节点代表的有几个元素</span></span><br><span class="line">    public HashMap&lt;Element&lt;V&gt;,Integer&gt; sizeMap;</span><br><span class="line"></span><br><span class="line">    public <span class="constructor">UnionFindSet(List&lt;V&gt; <span class="params">list</span>)</span>&#123;</span><br><span class="line">        elementMap = <span class="keyword">new</span> HashMap&lt;&gt;<span class="literal">()</span>;</span><br><span class="line">        fatherMap = <span class="keyword">new</span> HashMap&lt;&gt;<span class="literal">()</span>;</span><br><span class="line">        sizeMap = <span class="keyword">new</span> HashMap&lt;&gt;<span class="literal">()</span>;</span><br><span class="line">        <span class="comment">//初始化，都将每个元素设置为一个集合</span></span><br><span class="line">        <span class="keyword">for</span>(V value : <span class="built_in">list</span>)&#123;</span><br><span class="line">            Element&lt;V&gt; element = <span class="keyword">new</span> Element&lt;V&gt;(value);</span><br><span class="line">            elementMap.put(value,element);</span><br><span class="line">            father.put(element,element);</span><br><span class="line">            sizeMap.put(element,<span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">public boolean is<span class="constructor">SameSet(V <span class="params">a</span>,V <span class="params">b</span>)</span>&#123;</span><br><span class="line">    <span class="comment">//并查集的前提是有初始化，如果用户给的样本没有被初始化过，就没办法告诉用户该元素是否在集合中。</span></span><br><span class="line">    <span class="keyword">if</span>(elementMap.contains<span class="constructor">Key(<span class="params">a</span>)</span><span class="operator"> &amp;&amp; </span>elementMap.contains<span class="constructor">Key(<span class="params">b</span>)</span>)&#123;</span><br><span class="line">        return find<span class="constructor">Head(<span class="params">elementMap</span>.<span class="params">get</span>(<span class="params">a</span>)</span>)<span class="operator"> == </span>find<span class="constructor">Head(<span class="params">elementMap</span>.<span class="params">get</span>(<span class="params">b</span>)</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    return <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br><span class="line">public void union(V a,V b)&#123;</span><br><span class="line">    <span class="keyword">if</span>(elementMap.contains<span class="constructor">Key(<span class="params">a</span>)</span><span class="operator"> &amp;&amp; </span>elementMap.contains<span class="constructor">Key(<span class="params">b</span>)</span>)&#123;</span><br><span class="line">        Element&lt;V&gt; aF = find<span class="constructor">Head(<span class="params">elementMap</span>.<span class="params">get</span>(<span class="params">a</span>)</span>);</span><br><span class="line">        Element&lt;V&gt; bF = find<span class="constructor">Head(<span class="params">elementMap</span>.<span class="params">get</span>(<span class="params">b</span>)</span>);</span><br><span class="line">        <span class="keyword">if</span>(aF != bF)&#123;</span><br><span class="line">            Element&lt;V&gt; big = sizeMap.get(aF) &gt;= sizeMap.get(bF) ? aF : bF;</span><br><span class="line">            Element&lt;V&gt; small = big<span class="operator"> == </span>aF ? bF : aF;</span><br><span class="line">            fatherMap.put(small,big);</span><br><span class="line">            sizeMap.put(big,sizeMap.get(aF) + sizeMap.get(bF));</span><br><span class="line">            <span class="comment">//这个时候这个节点已经不是代表节点了，所以要把它从代表节点的集合中删掉。</span></span><br><span class="line">            sizeMap.remove(small);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">public Element&lt;V&gt; find<span class="constructor">Head(Element&lt;V&gt; <span class="params">element</span>)</span>&#123;</span><br><span class="line">    Stack&lt;Element&lt;V&gt;&gt; path = <span class="keyword">new</span> Stack&lt;&gt;<span class="literal">()</span>;</span><br><span class="line">    <span class="keyword">while</span>(element != fatherMap.get(element))&#123;</span><br><span class="line">        path.push(element);</span><br><span class="line">        element = fatherMap.get(element);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//将路径中所有节点的父设置成对顶部元素的。</span></span><br><span class="line">    <span class="keyword">while</span>(!path.is<span class="constructor">Empty()</span>)&#123;</span><br><span class="line">        fatherMap.put(path.pop<span class="literal">()</span>,element);</span><br><span class="line">    &#125;</span><br><span class="line">    return element;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>如何设计一个并行算法解决上述那个问题：</p>
<p>这样去思考，先将矩阵切成两半，然后用两个CPU去统计各自的那一半</p>
<p>然后收集被感染点感染的边界的点。</p>
<p>找到所有的被感染点感染的边界的点，让他们各自成为一个集合。</p>
<p>如果发现有两个集合是因为被切成两半才被分开的，那么就将这两个集合合并成一个集合。最后看有几个集合就有几个岛。</p>
<hr>
<h2 id="KMP算法解决的问题"><a href="#KMP算法解决的问题" class="headerlink" title="KMP算法解决的问题"></a><strong>KMP算法解决的问题</strong></h2><p>KMP用来求子串问题</p>
<p>字符串str1和str2，str1是否包含str2，如果包含返回str2在str1中开始的位置。如何做到时间复杂度O(N)完成？</p>
<p>阐述概念:</p>
<p>最长的前缀和后缀的匹配长度</p>
<p>举例:abbabbk</p>
<p>前缀长度为1时，a。此时后缀为b</p>
<p>前缀长度为2时，ab，此时后缀bb</p>
<p>前缀长度为3时，abb，此时后缀abb  此时两者相等。</p>
<p>前缀长度为4时，abba，此时后缀babb</p>
<p>前缀长度为5时，abbab，此时后缀bbabb</p>
<p>前缀长度为6时，不讨论</p>
<p>则k的前缀和后缀相等的最大长度为3。</p>
<p><a target="_blank" rel="noopener" href="https://www.bilibili.com/video/BV1kQ4y1h7ok?p=12&amp;share_source=copy_web">https://www.bilibili.com/video/BV1kQ4y1h7ok?p=12&amp;share_source=copy_web</a><br><figure class="highlight axapta"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="built_in">int</span> getIndexOf(String s,String m)&#123;</span><br><span class="line">    <span class="keyword">if</span>(s == <span class="literal">null</span> || m == <span class="literal">null</span> || m.length() &lt; <span class="number">1</span> || s.length() &lt; m.length())&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">char</span>[] str1 = s.toCharArray();</span><br><span class="line">    <span class="built_in">char</span>[] str2 = m.toCharArray();</span><br><span class="line">    <span class="built_in">int</span> i1 = <span class="number">0</span>;<span class="comment">//str1来到的位置</span></span><br><span class="line">    <span class="built_in">int</span> i2 = <span class="number">0</span>;<span class="comment">//str2来到的位置</span></span><br><span class="line">    <span class="built_in">int</span>[] <span class="keyword">next</span> = getNextArray(str2);</span><br><span class="line">    <span class="comment">//如果i1越界，代表匹配失败，如果i2越界，代表匹配成功</span></span><br><span class="line">    <span class="keyword">while</span>(i1 &lt; str1.length &amp;&amp; i2 &lt; str2.length)&#123;</span><br><span class="line">        <span class="keyword">if</span>(str1[i1] == str2[i2])&#123;</span><br><span class="line">            <span class="comment">//两者相同时，同时往前跳</span></span><br><span class="line">            i1++;</span><br><span class="line">            i2++;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(<span class="keyword">next</span>[i2] == <span class="number">-1</span>)&#123;<span class="comment">//next[i2] == -1代表i2是出于0位置的</span></span><br><span class="line">            <span class="comment">//也就是说我i2已经到0位置的时候还与i1位置上的数配不出来，那么i1就加1再去检查</span></span><br><span class="line">            i1++;</span><br><span class="line">        &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">//i2还能继续往右推，所以就继续右推</span></span><br><span class="line">            i2 = <span class="keyword">next</span>[i2];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//i2越界了，i1-i2就是相匹配的开头</span></span><br><span class="line">    <span class="comment">//i2越界了，返回-1</span></span><br><span class="line">    <span class="keyword">return</span> i2 == str2.length ? i1 - i2 : <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="built_in">int</span>[] getNextArray(<span class="built_in">char</span>[] ms)&#123;</span><br><span class="line">    <span class="keyword">if</span>(ms.length == <span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="built_in">int</span>[]&#123;<span class="number">-1</span>&#125;;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">int</span>[] <span class="keyword">next</span>= <span class="keyword">new</span> <span class="built_in">int</span>[ms.length];</span><br><span class="line">    <span class="keyword">next</span>[<span class="number">0</span>] = <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">next</span>[<span class="number">1</span>] = <span class="number">0</span>;<span class="comment">//因为前缀不能取到整体，所以为0</span></span><br><span class="line">    <span class="built_in">int</span> i = <span class="number">2</span>;</span><br><span class="line">    <span class="built_in">int</span> cn = <span class="number">0</span>;<span class="comment">//cn是你要拿哪个位置的字符和i-1位置的字符比对</span></span><br><span class="line">    <span class="keyword">while</span>(i &lt; <span class="keyword">next</span>.length)&#123;</span><br><span class="line">        <span class="keyword">if</span>(ms[i<span class="number">-1</span>] == ms[cn])&#123;</span><br><span class="line">            <span class="keyword">next</span>[i++] = ++cn;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(cn &gt; <span class="number">0</span>)&#123;</span><br><span class="line">            cn = <span class="keyword">next</span>[cn];</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">next</span>[i++] = <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">next</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="Manacher算法"><a href="#Manacher算法" class="headerlink" title="Manacher算法"></a><strong>Manacher算法</strong></h2><p>Manacher算法的核心是它的回文数组，这个回文数组不仅能帮助解决字符串回文问题，很多回文问题都可以用Manacher算法求</p>
<p>对于一个字符串 a b a b a b a a b a</p>
<p>给字符串中的每个字符加额外的符号，使得不管这个字符串的长度是奇数还是偶数，都让它变成偶数，使得需要考虑的情况只有一种(偶数情况)</p>
<pre><code>#a#b#a#b#a#b#a#a#b#a#
</code></pre><p>对字符串中每个字符的半径记录下来组成一个数组</p>
<p>记录下在字符串中对其取得的最远边界时的中心点C和所能扩大的最右侧的点R</p>
<p><strong>求回文子串的方式</strong></p>
<p><strong>讨论</strong></p>
<ol>
<li><p>在遍历的过程中，如果某个点i，它没有在最右回文右边界里，只能暴力扩(R变大)</p>
</li>
<li><p>来到一个点i，在最右回文右边界内部。取得最右回文右边界的中心点C和与R关于C的对称点L。那么i的对称点i’也一定在(L,R)范围内。</p>
<ol>
<li><p>如果i点的对称点i’的半径也在(L,R)范围内，则可以得出i的回文半径 = i’的回文半径</p>
</li>
<li><p>i’的回文区域，有一部分在(L,R)范围外，则i的回文半径就是(i,R)</p>
</li>
<li><p>如果i’的回文左区域正好与L重合，则i的回文半径至少为(i,R)，但不知道能不能到达更远，需要从R之外的字符开始再往外扩，然后确定答案(R可能变大)</p>
</li>
</ol>
</li>
</ol>
<figure class="highlight processing"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">char</span>[] <span class="title function_">manacherString</span>(<span class="built_in">String</span> <span class="built_in">str</span>)&#123;</span><br><span class="line">    <span class="type">char</span>[] charArr = <span class="built_in">str</span>.<span class="property">toCharArray</span>();</span><br><span class="line">    <span class="type">char</span>[] res = <span class="keyword">new </span><span class="class title_">char</span>[<span class="built_in">str</span>.<span class="property">length</span>() * <span class="number">2</span> + <span class="number">1</span>];</span><br><span class="line">    <span class="type">int</span> index = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i != res.<span class="property">length</span>; i++)&#123;</span><br><span class="line">        res[i] = (i &amp; <span class="number">1</span>) == <span class="number">0</span> ? <span class="string">&#x27;#&#x27;</span> : charArr[index++];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">maxLcpsLength</span>(<span class="built_in">String</span> s)&#123;</span><br><span class="line">    <span class="keyword">if</span>(s == <span class="literal">null</span> || s.<span class="property">length</span>() == <span class="number">0</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="type">char</span>[] <span class="built_in">str</span> = <span class="title function_">manacherString</span>(s);<span class="comment">//加特殊字符的方法 1221 --&gt; #1#2#2#1#</span></span><br><span class="line">    <span class="type">int</span>[] pArr = <span class="keyword">new </span><span class="class title_">int</span>[<span class="built_in">str</span>.<span class="property">length</span>];<span class="comment">//回文半径数组</span></span><br><span class="line">    <span class="type">int</span> C = <span class="number">-1</span>;<span class="comment">//中心</span></span><br><span class="line">    <span class="type">int</span> R = <span class="number">-1</span>;<span class="comment">//回文右边界的再往右一个位置 最右的有效区是R-1位置</span></span><br><span class="line">    <span class="type">int</span> <span class="built_in">max</span> = Integer.<span class="property">MIN_VALUE</span>；<span class="comment">//扩出来的最大值</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i != <span class="built_in">str</span>.<span class="property">length</span>; i++)&#123;<span class="comment">//每一个位置都求回文半径</span></span><br><span class="line">        <span class="comment">//i至少的回文区域，先给pArr[i]</span></span><br><span class="line">        <span class="comment">//R &gt; i 证明i在R内,否则至少不用验证的区域是1(自己和自己构成回文串)</span></span><br><span class="line">        pArr[i] = R &gt; i ? Math.<span class="property">min</span>(pArr[<span class="number">2</span>*C - i],R - i) : <span class="number">1</span>;</span><br><span class="line">        <span class="comment">//暴力循环</span></span><br><span class="line">        <span class="keyword">while</span>(i + pArr[i] &lt; <span class="built_in">str</span>.<span class="property">length</span> &amp;&amp; i - pArr[i] &gt; <span class="number">-1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span>(<span class="built_in">str</span>[i + pArr[i]] == <span class="built_in">str</span>[i - pArr[i]])</span><br><span class="line">                pArr[i]++;</span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(i + pArr[i] &gt; R)&#123;</span><br><span class="line">            R = i + pArr[i];</span><br><span class="line">            C = i;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">max</span> = Math.<span class="property">max</span>(<span class="built_in">max</span>,pArr[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">max</span> - <span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="滑动窗口"><a href="#滑动窗口" class="headerlink" title="滑动窗口"></a><strong>滑动窗口</strong></h2><ol>
<li><p>窗口的左边界为L，右边界为R。左边界和右边界可以在一系列数之间滑动，而且左边界一定不能超过右边界。</p>
</li>
<li><p>设置一个双端队列，双端队列的头部和尾部都可以弹出和进入。双端队列严格遵照单调性，头部高、尾部低。</p>
</li>
<li><p>如果窗口滑动，进入双端队列的数破坏了双端队列的单调性了，就从尾部弹出比我要放进去的数小的数，直到不破坏单调性为止。</p>
</li>
<li><p>头部一直维持滑动窗口的最大数</p>
</li>
<li><p>双端队列只存储数组中数的下标，不存放具体的值</p>
</li>
<li><p>双端队列中存储的是可能成为最大值的值</p>
</li>
</ol>
<figure class="highlight axapta"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="built_in">int</span>[] getMaxWindow(<span class="built_in">int</span>[] arr, <span class="built_in">int</span> w) &#123;</span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">null</span> || w &lt; <span class="number">1</span> || arr.length &lt; w) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// qmax 窗口最大值的更新结构</span></span><br><span class="line">    <span class="comment">// 放下标</span></span><br><span class="line">    LinkedList&lt;Integer&gt; qmax = <span class="keyword">new</span> LinkedList&lt;Integer&gt;();</span><br><span class="line">    <span class="built_in">int</span>[] res = <span class="keyword">new</span> <span class="built_in">int</span>[arr.length - w + <span class="number">1</span>];</span><br><span class="line">    <span class="built_in">int</span> <span class="keyword">index</span> = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="built_in">int</span> R = <span class="number">0</span>; R &lt; arr.length; R++) &#123;</span><br><span class="line">        <span class="keyword">while</span> (!qmax.isEmpty() &amp;&amp; arr[qmax.peekLast()] &lt;= arr[R]) &#123;</span><br><span class="line">            qmax.pollLast();</span><br><span class="line">        &#125;</span><br><span class="line">        qmax.addLast(R);</span><br><span class="line">        <span class="keyword">if</span> (qmax.peekFirst() == R - w) &#123;</span><br><span class="line">            qmax.pollFirst();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (R &gt;= w - <span class="number">1</span>) &#123;</span><br><span class="line">            res[<span class="keyword">index</span>++] = arr[qmax.peekFirst()];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="单调栈"><a href="#单调栈" class="headerlink" title="单调栈"></a><strong>单调栈</strong></h2><p><strong>窗口内最大值与最小值更新结构的原理与实现——单调栈</strong></p>
<p>如果有一堆数，我想知道任意一个数，左边离他最近比它大的和右边离他最近比它大的。</p>
<p>可以用单调栈来实现这个问题。单调栈可以从栈顶到栈底单调递减，也可以单调递增，具体看业务需求。</p>
<p>无重复值情况下：</p>
<p>想要求一个数左边离他最近的比它大的数和右边理他最近的比它大的数，就从数组的0坐标依次将元素放入数组，当放入你要求的那个数的时候，在这个数下面的就是左边比你大的数，再继续放入，如果有一个数放入的时候需要这个元素弹出，那么这个数就是右边离你最近比你大的数。</p>
<p>可以通过数组依次遍历整个数组，然后记录下每个数左边离他最近比它大、右边离他最近比它大的数</p>
<p>有重复值情况下：</p>
<p>当遇到重复值进栈的时候，一定会与另一个相同值相遇，这时候两个的坐标合并，例如1下标为止的数为4，3下标为止下的数也是4，所以合并后为{1,4}，他们左边位置的最大值为1坐标下面的数，右边离他们最近的最大值为让他们弹出去的那个数。</p>
<h3 id="数组中累积和与最小值的乘积，假设叫做指标A。给定一个正数数组，且指标A最大的值"><a href="#数组中累积和与最小值的乘积，假设叫做指标A。给定一个正数数组，且指标A最大的值" class="headerlink" title="数组中累积和与最小值的乘积，假设叫做指标A。给定一个正数数组，且指标A最大的值"></a><strong>数组中累积和与最小值的乘积，假设叫做指标A。给定一个正数数组，且指标A最大的值</strong></h3><p>流程:假设子数组必须包含一个元素i，而且这个i一定要是这个子数组的最小值，那在候选选组中，哪一个指标是最大的。将每一个元素都当作子数组中的最小值，利用单调栈求出所以后比这个元素大的数的子数组，那么指标A的最大值一定在这些子数组中。</p>

    </div>

    
    
    

      <footer class="post-footer">
          <div class="post-tags">
              <a href="/wang-cheng/tags/%E5%B7%A6%E7%A5%9E/" rel="tag"># 左神</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/wang-cheng/2022/04/02/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%B8%89/" rel="prev" title="算法笔记(三)">
      <i class="fa fa-chevron-left"></i> 算法笔记(三)
    </a></div>
      <div class="post-nav-item">
    <a href="/wang-cheng/2022/04/05/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%BA%94/" rel="next" title="算法笔记(五)">
      算法笔记(五) <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E5%93%88%E5%B8%8C%E5%87%BD%E6%95%B0%E4%B8%8E%E5%93%88%E5%B8%8C%E8%A1%A8%E7%AD%89"><span class="nav-number">1.</span> <span class="nav-text">哈希函数与哈希表等</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%93%88%E5%B8%8C%E7%BB%93%E6%9E%84"><span class="nav-number">1.1.</span> <span class="nav-text">哈希结构</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%93%88%E5%B8%8C%E8%A1%A8%E7%9A%84%E5%AE%9E%E7%8E%B0"><span class="nav-number">1.2.</span> <span class="nav-text">哈希表的实现</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%93%88%E5%B8%8C%E8%A1%A8%E6%98%AF%E5%A6%82%E4%BD%95%E5%B0%86%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E9%80%BC%E8%BF%91%E4%B8%BAO-1-%E7%9A%84"><span class="nav-number">1.2.1.</span> <span class="nav-text">哈希表是如何将时间复杂度逼近为O(1)的</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%AF%A6%E8%A7%A3%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8"><span class="nav-number">1.3.</span> <span class="nav-text">详解布隆过滤器</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%AD%97%E8%8A%82-Byte-%E4%B8%8E%E6%AF%94%E7%89%B9-bit-%E4%B9%8B%E9%97%B4%E7%9A%84%E5%85%B3%E7%B3%BB"><span class="nav-number">1.3.1.</span> <span class="nav-text">字节(Byte)与比特(bit)之间的关系</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8%E7%9A%84%E5%8E%9F%E7%90%86"><span class="nav-number">1.3.2.</span> <span class="nav-text">布隆过滤器的原理</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%9D%A2%E8%AF%95%E4%B8%AD%E8%81%8A%E5%88%B0%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8"><span class="nav-number">1.3.3.</span> <span class="nav-text">面试中聊到布隆过滤器</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%B8%80%E8%87%B4%E6%80%A7%E5%93%88%E5%B8%8C%E5%8E%9F%E7%90%86"><span class="nav-number">1.4.</span> <span class="nav-text">一致性哈希原理</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%B8%80%E8%87%B4%E6%80%A7%E5%93%88%E5%B8%8C%E8%A7%A3%E5%86%B3"><span class="nav-number">1.4.1.</span> <span class="nav-text">一致性哈希解决</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%A7%A3%E5%86%B3%E4%B8%80%E8%87%B4%E6%80%A7%E5%93%88%E5%B8%8C%E5%AD%98%E5%9C%A8%E7%9A%84%E4%B8%A4%E4%B8%AA%E9%97%AE%E9%A2%98"><span class="nav-number">1.4.2.</span> <span class="nav-text">解决一致性哈希存在的两个问题</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B9%B6%E6%9F%A5%E9%9B%86"><span class="nav-number">1.5.</span> <span class="nav-text">并查集</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#KMP%E7%AE%97%E6%B3%95%E8%A7%A3%E5%86%B3%E7%9A%84%E9%97%AE%E9%A2%98"><span class="nav-number">1.6.</span> <span class="nav-text">KMP算法解决的问题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Manacher%E7%AE%97%E6%B3%95"><span class="nav-number">1.7.</span> <span class="nav-text">Manacher算法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3"><span class="nav-number">1.8.</span> <span class="nav-text">滑动窗口</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%8D%95%E8%B0%83%E6%A0%88"><span class="nav-number">1.9.</span> <span class="nav-text">单调栈</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%95%B0%E7%BB%84%E4%B8%AD%E7%B4%AF%E7%A7%AF%E5%92%8C%E4%B8%8E%E6%9C%80%E5%B0%8F%E5%80%BC%E7%9A%84%E4%B9%98%E7%A7%AF%EF%BC%8C%E5%81%87%E8%AE%BE%E5%8F%AB%E5%81%9A%E6%8C%87%E6%A0%87A%E3%80%82%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AA%E6%AD%A3%E6%95%B0%E6%95%B0%E7%BB%84%EF%BC%8C%E4%B8%94%E6%8C%87%E6%A0%87A%E6%9C%80%E5%A4%A7%E7%9A%84%E5%80%BC"><span class="nav-number">1.9.1.</span> <span class="nav-text">数组中累积和与最小值的乘积，假设叫做指标A。给定一个正数数组，且指标A最大的值</span></a></li></ol></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">王诚</p>
  <div class="site-description" itemprop="description">命运对勇士低语，你无法抵御风暴；勇士低声回应，我就是风暴</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/wang-cheng/archives/">
        
          <span class="site-state-item-count">32</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/wang-cheng/tags/">
          
        <span class="site-state-item-count">12</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">王诚</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/wang-cheng/lib/anime.min.js"></script>
  <script src="/wang-cheng/lib/velocity/velocity.min.js"></script>
  <script src="/wang-cheng/lib/velocity/velocity.ui.min.js"></script>

<script src="/wang-cheng/js/utils.js"></script>

<script src="/wang-cheng/js/motion.js"></script>


<script src="/wang-cheng/js/schemes/pisces.js"></script>


<script src="/wang-cheng/js/next-boot.js"></script>




  















  

  
      

<script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      loader: {
        source: {
          '[tex]/amsCd': '[tex]/amscd',
          '[tex]/AMScd': '[tex]/amscd'
        }
      },
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              let target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    (function () {
      var script = document.createElement('script');
      script.src = '//cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js';
      script.defer = true;
      document.head.appendChild(script);
    })();
  } else {
    MathJax.startup.document.state(0);
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  

</body>
</html>
